1. Field of the Invention
The present invention relates generally to methods and apparatus for performing bitmapped image registration (alignment). Such methods and apparatus may, for example, be used to register an incoming image (such as an image scanned into an image processing system via a paper scanner) with one of a set of reference bitmapped images (also referred to herein as "master" bitmapped images), accessible to the system.
More particularly, the invention relates to methods and apparatus for performing bitmapped image registration utilizing pre-computed gradients, based on which an incoming image may accurately be registered with a the master, in a computationally efficient manner.
2. Description of the Related Art
In the field of pattern recognition and document understanding, it is frequently necessary to identify a given bitmapped image as being similar to (or the same as) one of a set of master bitmapped images.
A straightforward pixel-by-pixel comparison is usually not practical because the image to be identified may not be registered accurately with the master. This can occur, for example, because of differences in document positioning during scanning. This misregistration is also a problem when specific regions in a document need to be read for further processing.
One well known approach to solving the image registration problem uses the principal axis transform, in which the distance between the centers of mass of the master and the image to be registered is computed.
An example of prior art methods and apparatus for solving the image registration problem utilizing a principal axis transform is set forth in U.S. Pat. No. 5,022,089, to Wilson, issued Jun. 4, 1991.
In particular, Wilson teaches an algorithmic based method and apparatus that uses a digital image gray level centroid ("center of gravity") to compute the center locations of symmetric crosshair register marks.
The difficulty with methods that attempt to solve registration problems utilizing principal axis transforms is that they are computationally complex expending computing resources unnecessarily, and they are easily defeated by extraneous material in the image which make the center of mass incorrect.
Accordingly, it would be desirable to provide methods and apparatus for solving bitmapped image registration problems in a manner that does not require the use of principal axis transforms or other processing techniques that are sensitive to extraneous material in the image being processed (registered).
In addition to the teachings of Wilson, many other techniques for solving image registration problems in image processing, character recognition and object alignment systems (all typically operating under software control), are well known by those skilled in the art.
By way of example, to illustrate the state of the art, reference is made to the teachings of Kumagai, set forth in U.S. Pat. No. 5,164,997, issued Nov. 17, 1992; U.S. Pat. No. 5,161,204 issued to Hutcheson et al., on Nov. 3, 1992; U.S. Pat. No. 4,905,296 issued to Nishihara on Feb. 27, 1990; U.S. Pat. No. 4,457,015 issued to Nally et al., on Jun. 26, 1984; and U.S. Pat. No. 4,680,627, issued to Sase et al., on Jul. 14, 1987.
U.S. Pat. No. 5,164,997 patent to Kumagai addresses the bitmapped image registration problem by using pixels of closed contours to align images. A series of pixels is selected from along a contour in each image and pixel series are compared to determine a degree of concurrence. One series is then shifted by one pixel relative to the other, and concurrence is again determined after the shift. The series are shifted repeatedly until all shifts have been measured. The shift distance that results in the maximum concurrence is selected as the measure of the amount of rotation needed to align the images.
After rotational alignment, one image is displaced by one pixel relative to the other and the displace images are compared to determine a degree of coincidence. After the images have been rotated and displaced, they are aligned.
Those skilled in the art will recognize that the teachings of Kumagai require the use of a computationally intensive processes related to contour extraction and data manipulation, along with all of the aforementioned tests for concurrence and coincidence. Furthermore, the accuracy of the technique taught by Kumagai depends on the accuracy of extracted contours.
Accordingly, it would desirable to provide methods and apparatus for solving bitmapped image registration problems accurately in a manner that does not require the extraction or manipulation of image contour data, and which does not rely upon the accuracy of contour data.
U.S. Pat. No. 5,161,204 to Hutcheson et al., relates to methods and apparatus which perform pattern recognition under software control. The pattern recognition system employs feature template regions and feature vectors. A Gaussian distribution of fixed intensities may be applied along with a gradient decent or steepest decent method which is used to track the convergence of each member of a training set of feature vectors.
The teachings of Hutcheson et al., however, require the use of a neural network to recognize two dimensional input images which are sufficiently similar to a database of previously stored two dimensional images (masters).
Accordingly, it would be desirable to provide methods and apparatus for solving bitmapped image registration problems in a manner that does not require without requiring the use of neural networks.
With respect to the remaining references referred to hereinabove, which illustrate the state of the art, U.S. Pat. No. 4,905,296 to Nishihara relates to an image processing system that employs a Gaussian Convolution operator to recognize shapes; U.S. Pat. No. 4,457,015 to Nally et al., relates to a character recognition system that employs template matching techniques for character recognition; and U.S. Pat. No. 4,680,627, to Sase et al., relates to a pattern checking apparatus wherein registration patterns of two different images are accurately compared using binary bit serial signals.
Those skilled in the art will recognize however, that none of the approaches set forth in the state of the art illustrative patents described hereinabove, teaches, claims or even suggests registering a bitmapped image against a master by gradient decent. Such an approach to bitmapped image registration, as will become clear with reference to the detailed description of the invention set forth hereinafter, provides a registration technique which is computationally efficient, insensitive to extra material in image to be registered, and is a simple process to use that may be applied to all bitmapped, monochrome images.